/*
题目描述
若两个正整数的和为素数，则这两个正整数称之为“素数伴侣”，如2和5、6和13，它们能应用于通信加密。
现在密码学会请你设计一个程序，从已有的 N （ N 为偶数）个正整数中挑选出若干对组成“素数伴侣”，
挑选方案多种多样，例如有4个正整数：2，5，6，13，如果将5和6分为一组中只能得到一组“素数伴侣”，
而将2和5、6和13编组将得到两组“素数伴侣”，能组成“素数伴侣”最多的方案称为“最佳方案”，当然密码学会希望你寻找出“最佳方案”。

输入:
有一个正偶数 n ，表示待挑选的自然数的个数。后面给出 n 个具体的数字。

输出:
输出一个整数 K ，表示你求得的“最佳方案”组成“素数伴侣”的对数。

输入：
    4
    2 5 6 13
输出：2
*/

#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
#include<string.h>
#define MAX_COUNT 100

int oddCount = 0;
int evenCount = 0;
int M[MAX_COUNT];
bool used[MAX_COUNT];
int network[MAX_COUNT][MAX_COUNT];
int odds[MAX_COUNT]; //奇数
int evens[MAX_COUNT]; //偶数

bool isprime(int figure) {
    int i;
    for (i = 2; i * i <= figure; i++) {
        if (figure % i == 0) {
            return false;
        }
    }

    return true;
}

void buildNetwork(int odds[], int evens[]) {
    int i, j;
    int figure;
    for (i = 0; i < oddCount; i++)
        for (j = 0; j < evenCount; j++) {
            figure = odds[i] + evens[j];
            if (isprime(figure)) {
                network[i][j] = 1;
            }
        }
}

int findp(int j) {
    for (int i = 0; i < oddCount; i++) {
        if (network[i][j] == 1 && (used[i] == 0)) {
            used[i] = 1;
            if (M[i] == -1 || findp(M[i])) {
                M[i] = j;
                return 1;
            }
        }
    }
    return 0;
}


int main() {
    int i, n, figure;
    scanf("%d", &n);

    memset(odds, -1, sizeof(odds));
    memset(evens, -1, sizeof(evens));
    for (i = 0; i < n; i++) {
        scanf("%d", &figure);
        if (figure % 2 == 0) {
            evens[evenCount++] = figure;
        } else {
            odds[oddCount++] = figure;
        }
    }
    buildNetwork(odds, evens);

    memset(M, -1, sizeof(M));
    int sum = 0;
    for (i = 0; i < evenCount; i++) {
        memset(used, 0, sizeof(used));
        sum = sum + findp(i);
    }

    printf("%d", sum);

    return 0;
}





